package com.company.fusai;

import java.util.*;
import java.util.stream.Collectors;

/**
 * BurgerSales
 *
 * @author jianf
 * @date 2021年09月13 18:12
 */
public class BurgerSales {

    public int maxIncomes(int[] coins){
        int p = 1;
        return  doRate(coins,p);
    }

    public int doRate(int[] coins,int price){
        int money=0;
        int curMoney=0;
        for (int i = 0; i < coins.length; i++) {
            if(coins[i]>= price){
                curMoney += price;
            }
        }
        if(curMoney <=0){
            return money;
        }
        if(curMoney >= money){
            money = curMoney;
        }
        curMoney = doRate(coins,price+1);
        if(curMoney >= money){
            money = curMoney;
        }
        return money;
    }

    /**
     * 第二种算法
     * @param coins
     */
    public int maxIncomes1(int[] coins){

        Map<Integer,Integer> moneyNum = new HashMap<>();
        int result = 0;
        for (int i = 0; i < coins.length ; i++) {
            if (moneyNum.containsKey(coins[i])){
                moneyNum.put(coins[i],moneyNum.get(coins[i])+1);
            }else{
                moneyNum.put(coins[i],1);
            }
        }
        List<Integer> keyList = moneyNum.keySet().stream()
                .sorted(Comparator.naturalOrder()).collect(Collectors.toList());
        for (int i = 0; i < keyList.size(); i++) {
            for (int j = i+1; j < keyList.size(); j++) {
                if (keyList.get(i)<=keyList.get(j)){
                    moneyNum.put(keyList.get(i),moneyNum.get(keyList.get(i))+moneyNum.get(keyList.get(j)));
                }
            }
            int tmp = keyList.get(i)* moneyNum.get(keyList.get(i));
            if(tmp > result){
                result = tmp;
            }
        }
        return result;
    }

    public static void main(String[] args) {
//        int[] coins = new int[]{4,1,1};
        int[] coins = new int[]{4,3,1};
        BurgerSales burgerSales = new BurgerSales();
        System.out.println("最大利润为；"+burgerSales.maxIncomes1(coins));
    }
}
